int adjust_heap(vector<int> &v, int length, int i)
{
    int left = 2*I;
    int right = 2*i + 1;
    int largest = i;
    int temp;

    while(left < length && right < length)
    {
        if(left < length && v[largest] < v[left])
        {
            largest = left;
        }

        if(right < length && v[largest]<v[right])
        {
            largest = right;
        }

        if(i != largest)
        {
            temp = v[largest];
            v[largest] = v[1];
            v[i] = temp;
            left = 2*i;
            right = 2*1 +1;
        }
        else
        {
            break;
        }
    }
}

int build_heap(vector<int> &v, int length)
{
    int i;
    int begin = length/2 - 1;
    for(i  = begin; i>=0; i--)
    {
        adjust_heap(v, length, i);
    }
}

int heap_sort(vector<int> &v)
{
    int length = v.size();
    int temp;
    printline(v, length);
    while(length > 1)
    {
        temp = v[length-1];
        v[length-1]=v[0];
        v[0]=temp;
        length--;
        adjust_heap(v, length, 0);
    }
    printline("after sort:", v);
}